class Solution:
    def numWays(self, n: int) -> int:
        if(n < 2):
            return 1
        dp = [1, 2]
        for i in range(2, n):
            dp.append(dp[i-1]+dp[i-2])
        return dp[n-1]%1000000007


if __name__ == "__main__":
    print(Solution().numWays(2))
    print(Solution().numWays(7))
    # 134903163
    print(Solution().numWays(44))
